package com.zjl.redis.第14章_大数据统计;

import org.apache.curator.shaded.com.google.common.hash.BloomFilter;
import org.apache.curator.shaded.com.google.common.hash.Funnels;

/**
 * 布隆过滤器(英语: Bloom Filter)是1970年由布隆提出的。
 * 它实际上是一个很长的工:进制数组00000000)+一系列随机hash算法映射函数，主要用于判断一个元素是否在集合中。
 *
 * 通常我们会遇到很多要判断一个 元素是否在某个集合中的业务场景，
 * 一般想到的是将 集合中所有元素保存起来，然后通过比较确定。
 * 链表、网、哈希表等等数据结构都是这种思路。
 * 但是随着集合中元素的增加，我们需要的存储空间也会呈现线性增长，最终达到瓶颈。
 * 同时检索速度也越来越慢,上述三种结构的检索时间复杂度分别为O(n),O(logn),0(1)。
 * 这个时候，布隆过滤器(Bloom Filter) 就应运而生
 *
 * *************************特点*****************************：
 *      高效地插入和查询，占用空间少，返回的结果是不确定性+不够完美。
 *      一个元素如果判断结果:
 *              存在时，元素不一定存在, 但是判断结果为不存在时,则一定不存在。
 * 布隆过滤器可以添加元素，但是不能删除元素，
 * 由于涉及hashcode判断依据，删掉元素会导致误判率增加。
 *
 *
 * 布隆过滤器(BloomFilter)是一种专用来解决去重问题的高级数据结构。
 * 实质就是一个大型位数组和几个不同的无偏hash函数(无偏表示分布均匀)。
 * 由一个初值都为零的bit数组和多个个哈希函数构成，用
 * 来快速判断某个数据是否存在。
 * 但是跟HyperLogLog一样，它也一样有那么一点点不精确，也存在一定的误判概率.
 *
 *
 */
public class C3_布隆过滤器底层 {

    private static int size = 1000000;//预计要插入多少数据

    private static double fpp = 0.0001;//期望的误判率  也就是假阳性

    /**
     * @see                           com.google.common.hash.BloomFilter
     * @see org.apache.curator.shaded.com.google.common.hash.BloomFilter
     * 只能说能说一模一样
     */
    private static BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), size, fpp);
    public static void main(String[] args) {
        //hash  碰撞
        System.out.println("Aa".hashCode());
        System.out.println("BB".hashCode());

        System.out.println("柳柴".hashCode());
        System.out.println("柴柕".hashCode());

        System.out.println("------------------------------------------");

        int count = 0;
        bloomFilter.mightContain(5);//判断是否存在
        bloomFilter.put(5);//添加数据，并返回是否添加成功
        for (int i = 0; i < 1000000; i++) {
            if (!bloomFilter.put(i)) {
                count++;
                System.out.println(i + " 误存在");
            }
        }
        System.out.println("总共的误存在数 : " + count);
    }


}
